﻿using CodeTop.八股;
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace CodeTop.复习十月份
{
    public class Solution1314
    {
        public int[][] MatrixBlockSum(int[][] mat, int k)
        {
            int m = mat.Length;
            int n = mat[0].Length;
            int[][] dp = new int[m][];
            int[][] res = new int[m][];
            for (int i = 0; i < m; i++)
            {
                dp[i] = new int[n];
                res[i] = new int[n];
            }

            dp[0][0] = mat[0][0];
            for (int i = 1; i < m; i++)
            {
                dp[i][0] = dp[i - 1][0] + mat[i][0];
            }
            for (int i = 1; i < n; i++)
            {
                dp[0][i] = dp[0][i - 1] + mat[0][i];
            }

            //先生成前缀和
            for (int i = 1; i < m; i++)
            {
                for (int j = 1; j < n; j++)
                {
                    dp[i][j] = mat[i][j] + dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1];
                }
            }

            //计算结果
            for (int i = 0; i < m; i++)
            {
                for (int j = 0; j < n; j++)
                {
                    int leftbottom = 0;
                    int righttop = 0;
                    int lefttop = 0;
                    //计算当前矩阵的右下角
                    int right = j + k;
                    int left = j - k;
                    int bottom = i + k;
                    int top = i - k;

                    if (right >= n)
                    {
                        right = n - 1;
                    }

                    if (bottom >= m)
                    {
                        bottom = m - 1;
                    }
                    if (left < 1)
                    {
                        leftbottom = 0;
                    }
                    else
                    {
                        leftbottom = dp[bottom][left - 1];
                    }

                    if (top < 1)
                    {
                        righttop = 0;
                    }
                    else
                    {
                        righttop = dp[top - 1][right];
                    }
                    if (left < 1 || top < 1)
                    {
                        lefttop = 0;
                    }
                    else
                    {
                        lefttop = dp[top - 1][left - 1];
                    }
                    Console.WriteLine(dp[bottom][right] + "," + leftbottom + "," + righttop + "," + lefttop);

                    // res[bottom][right] = dp[bottom][right] - dp[bottom][left - 1] - dp[top - 1][right] + dp[top - 1][left - 1];
                    res[i][j] = dp[bottom][right] - leftbottom - righttop + lefttop;
                }
            }

            return res;
        }
    }

    public class Program1314
    {
        private static void Main(string[] args)
        {
            int[][] mat = [[1, 2, 3], [4, 5, 6], [7, 8, 9]];
            int k = 1;
            Solution1314 solution1314 = new Solution1314();
            int[][] res = solution1314.MatrixBlockSum(mat, k);
            for (int i = 0; i < res.Length; i++)
            {
                for (int j = 0; j < res[i].Length; j++)
                {
                    Console.Write(res[i][j] + ",");
                }
                Console.WriteLine();
            }
        }
    }
}